The present invention relates to processing systems for three-dimensional computer graphics displays.
Three-dimensional computer graphics displays are used to display images to a user as if he were observing a real world environment. These systems store in a data base a representation in three-dimensional coordinates of three-dimensional objects, as well as their color and other properties. Additional "environment" information including the number, color, location, and other properties of illumination sources, atmospheric properties, and many other details may also be specified. The display is produced after being provided with the desired viewing angle for the viewer. The system must calculate all the details of the image, including determining which objects obscure others from the viewer's point of view, and present them accordingly.
A typical graphics display system is shown in FIG. 1. An image data base 12 stores a description of the objects in the scene. The objects are described with a number of small polygons which cover the surface of the object in the same manner that a number of small tiles can cover a wall or other surface. Each polygon is described as a list of vertex coordinates (X, Y, Z in "Model" coordinates) and some specification of material surface properties (i.e., color, texture, shininess, etc.), as well as possibly the normal vectors to the surface at each vertex. For three-dimensional objects with complex curved surfaces, the polygons in general must be triangles or quadralaterals, and the latter can always be decomposed into pairs of triangles.
A transformation engine 14 transforms the object coordinates in response to the angle of viewing selected by a user from user input 16. In addition, the user may specify the field of view, the size of the image to be produced, and the back end of the viewing volume so as to include or eliminate background as desired.
Once this viewing area has been selected, a clipping circuit 18 eliminates the polygons (i.e., triangles) which are outside the viewing area and "clips" the polygons which are partly inside and partly outside the viewing area. These clipped polygons will correspond to the portion of the polygon inside the viewing area with new edge(s) corresponding to the edge(s) of the viewing area. The polygon vertices are then transmitted to the next stage in coordinates corresponding to the viewing screen (in X, Y coordinates) with an associated depth for each vertex (the Z coordinate). In a typical system, the lighting model 20 is next applied taking into account the light sources 22. The polygons with their color values are then transmitted to a rasterizer 24.
For each polygon, rasterizer 24 determines which pixel positions are covered by the polygon and attempts to write the associated color values and depth (Z value) into frame buffer 26. Rasterizer 24 compares the depth values (Z) for the polygon being processed with the depth value of a pixel which may already be written into the frame buffer. If the depth value of the new polygon pixel is smaller, indicating that it is in front of the polygon already written into the frame buffer, then its value will replace the value in the frame buffer because the new polygon will obscure the polygon previously processed and written into the frame buffer. This process is repeated until all of the polygons have been rasterized. At that point, video controller 28 displays the contents of frame buffer 26 on a display 30 a scan line at a time in raster order.
A number of systems have been designed to improve upon the basic system of FIG. 1. With recent improvements in floating point processing and polygon fill algorithms, the main bottleneck of the system is the amount of time required to rasterize each polygon, compare it to what is already stored in the frame buffer, and then write it into the frame buffer. The time required to repeat this process for each polygon is substantial.
A basic method is characterized by a single rasterization processor writing pixels one by one into a DRAM frame buffer array. The improved systems are characterized by employing a large number of processors in parallel in which the individual processors represent pixels in the frame buffer. These systems differ in how the processors are assigned to pixels.
The pixel-planes method employs brute force, and assigns a processor for every pixel in the display screen, as set forth in Foulton, et al., Pixel-Planes: Building a VLSI-Based Graphics System, 1985 Chapel Hill Conference on Very large Scale Integration 35 (H. Fuchs ed, 1985). The edges of two dimensional polygon descriptions are sent one by one to the pixel processors. The processors determine which side of each edge they are on, and consider themselves inside a particular polygon only if they are on the correct side of all its edges. Having determined membership for a given polygon, the pixel processors next load interpolated depth and color information inside their pixel value register, so long as the depth information is less than that of any previously stored pixel value. When all polygons have been processed, the information stored at each pixel is supplied to the display in raster scan order. This system has the advantage in speed over the system in FIG. 1 in that the drawing time for any polygon (with a fixed number of sides) is constant, regardless of the number of pixels effected by the polygon (the area of the polygon). The disadvantage is that an extremely large number of processors is needed. For instance, a 1Kx1K display would require in excess of one million processors. This disadvantage is only somewhat mitigated by placing multiple pixel processors on a single chip.
The Scan Line Access Memory (SLAM) still requires custom storage registers for each pixel in the display, but only contains enough pixel processors for a single scan line. It is set forth in Demetrescu, High Speed Image Rasterization Using Scan Line Access Memories, 1985 Chapel Hill Conference on Very Large Scale Integration 35 (H. Fuchs ed, 1985). The idea here is to use external rasterization hardware to break up each polygon into horizontal runs of pixels. Only the start and stop addresses of these runs are entered into the SLAM chips, the internal one dimensional array of pixel processors determines which pixels are covered by this run. The results are written into an on-chip memory array of pixel values, indexed by the y location of this particular run. When all the polygons have been processed, internal double buffering allows the information stored at each pixel to be supplied to the display in raster scan order. This system has the advantage that large polygons can be rasterized in time mostly only dependent upon their height, not their area. The smaller number of pixel processors reduces the number of chips needed compared to pixel planes. However, the system does have several disadvantages. Considerable external circuitry must break up polygons into pixel runs, and sequence this data to the SLAM chips. The line by line overhead required per polygon reduces the overall speed of the system. Finally, the requirement for on-chip RAM resources for all pixel effected by the local pixel processors still means that an exorbitant number of chips are needed to make a functioning 1Kx1K system.
The super buffer also employs a single scan line of pixel processors, but does not require local memory for all the pixels effected by them to be on the same chip. It is set forth in Gharachorloo and Pottle, Super Buffer: A Systolic VLSI Graphics Engine for Real Time Raster Image Generation, 1985 Chapel Hill Conference on Very Large Scale Integration 35 (H. Fuchs ed, 1985). The previous two systems take input polygons one at a time, rasterizing each one completely before going on to the next. The super buffer requires all the polygons to be displayed to be presorted by the y scan line they first appear on. Each polygon is broken up into runs on a scan line basis, and the runs sent to the pipe of pixel processors. The trick is to send all the runs for all polygons for a given scan line before sending any runs for any further scan lines. This requires a buffer of partially rasterized polygons to be kept. This system has the advantage that the time to rasterize a given polygon is as in SLAM: dependent only on the height of the polygon, and not its area. It also has the advantage that the number of chips required by a system is considerably lower than in the other two systems. However, it has several disadvantages. It shares SLAM's requirement for an off-chip polygon run generator, and adds the requirement for juggling several active polygons at a time within this generator. A further requirement is an off-chip memory subsystem to store and sort by starting y scan line all the polygons to be displayed.